package master2;

/**
 * @author chenyw
 * @date 2022/9/24 21:03
 * 丑数
 */
public class M263isUgly {

    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 5 == 0) {
            n /= 5;
        }
        while (n % 3 == 0) {
            n /= 3;
        }
        while (n % 2 == 0) {
            n /= 2;
        }
        return n == 1;
    }

/*    //超出内存限制，不能用dp数组
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        boolean[] dp = new boolean[n + 1];
        if (n < 7) {
            return true;
        }
        for (int i = 1; i < 7; i++) {
            dp[i] = true;
        }
        for (int i = 7; i <= n; i++) {
            boolean flag = false;
            if (i % 2 == 0) {
                flag = dp[i / 2] ? true : false;
            }
            if (i % 3 == 0 && !flag) {
                flag = dp[i / 3] ? true : false;
            }
            if (i % 5 == 0 && !flag) {
                flag = dp[i / 5] ? true : false;
            }
            if (flag) {
                dp[i] = true;
            }
        }
        return dp[n - 1];
    }*/
}
